Binary Tree হল একটি ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডে সর্বাধিক দুটি সন্তান (left এবং right) থাকতে পারে। এটি একটি গঠন যা ডেটা সংগঠনের জন্য ব্যবহৃত হয় এবং বিভিন্ন এলগরিদম এবং সমস্যার সমাধানে গুরুত্বপূর্ণ ভূমিকা পালন করে। নিচে বাইনারি ট্রির মৌলিক ধারণা, গঠন, প্রকারভেদ এবং ট্রাভার্সাল পদ্ধতির বিশ্লেষণ করা হলো।
১. Binary Tree এর গঠন
১.১ Node Structure
একটি বাইনারি ট্রির নোড সাধারণত তিনটি অংশ নিয়ে গঠিত:
- ডেটা (Data): নোডের মধ্যে সংরক্ষিত মান।
- বাম সন্তান (Left Child): নোডের বাম দিকে অবস্থিত শিশু নোড।
- ডান সন্তান (Right Child): নোডের ডান দিকে অবস্থিত শিশু নোড।
typedef struct Node {
int data; // নোডের ডেটা
struct Node *left; // বাম সন্তান
struct Node *right; // ডান সন্তান
} Node;
১.২ Binary Tree এর গঠন
বাইনারি ট্রি সাধারণত একটি হেড নোড দ্বারা শুরু হয়, এবং প্রতিটি নোডে দুটি সন্তানের জন্য স্থান বরাদ্দ থাকে।
২. Binary Tree এর প্রকারভেদ
২.১ পূর্ণ বাইনারি ট্রি (Full Binary Tree)
এটি এমন একটি বাইনারি ট্রি যেখানে প্রতিটি নোডের শূন্য বা দুটি সন্তান থাকে।
২.২ সম্পূর্ণ বাইনারি ট্রি (Complete Binary Tree)
এটি একটি বাইনারি ট্রি যেখানে সব স্তরের নোড সম্পূর্ণভাবে পূর্ণ থাকে, তবে শেষ স্তরের নোড বামদিকে পূর্ণ থাকে।
২.৩ ব্যালেন্সড বাইনারি ট্রি (Balanced Binary Tree)
এটি এমন একটি ট্রি যেখানে প্রতিটি নোডের বাম এবং ডান সাবট্রির উচ্চতার মধ্যে সর্বাধিক এক স্তরের পার্থক্য থাকে।
২.৪ বাইনারি অনুসন্ধান ট্রি (Binary Search Tree)
এটি একটি বিশেষ ধরনের বাইনারি ট্রি যেখানে প্রতিটি নোডের বাম সন্তানের মান তার নিজস্ব মানের থেকে ছোট এবং ডান সন্তানের মান বড় হয়।
৩. Binary Tree এর ট্রাভার্সাল পদ্ধতি
বাইনারি ট্রির নোডগুলিকে এক বা একাধিকভাবে পরিদর্শন করতে তিনটি প্রধান পদ্ধতি রয়েছে:
৩.১ ইনঅর্ডার ট্রাভার্সাল (In-Order Traversal)
- প্রক্রিয়া: বাম শিশু -> মূল নোড -> ডান শিশু
- এটি একটি বাইনারি অনুসন্ধান ট্রির জন্য সাজানো ডেটা প্রদান করে।
৩.২ প্রি-অর্ডার ট্রাভার্সাল (Pre-Order Traversal)
- প্রক্রিয়া: মূল নোড -> বাম শিশু -> ডান শিশু
- এটি ডেটা কাঠামোর সংরক্ষণের জন্য ব্যবহৃত হয়।
৩.৩ পোস্ট-অর্ডার ট্রাভার্সাল (Post-Order Traversal)
- প্রক্রিয়া: বাম শিশু -> ডান শিশু -> মূল নোড
- এটি নোড মুছে ফেলার সময় ব্যবহার করা হয়।
৩.৪ স্তর অনুযায়ী ট্রাভার্সাল (Level Order Traversal)
- এই পদ্ধতিতে, ট্রি স্তর অনুযায়ী পরিদর্শন করা হয়। প্রথমে শিকড়, তারপর প্রথম স্তর, তারপরে দ্বিতীয় স্তর ইত্যাদি।
Read more
